package demo7;

import java.util.*;

class GraphList {
    private LinkedList<Integer>[] adjList; // 邻接表
    private char[] vertices;   // 顶点
    private int vexnum;        // 顶点数

    // 构造函数，初始化邻接表
    public GraphList(int vexnum) {
        this.vexnum = vexnum;
        adjList = new LinkedList[vexnum];
        vertices = new char[vexnum];
        for (int i = 0; i < vexnum; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 设置顶点
    public void setVertex(int index, char data) {
        vertices[index] = data;
    }

    // 添加边
    public void addEdge(int i, int j) {
        adjList[i].add(j);
        adjList[j].add(i); // 无向图，i到j和j到i的边都添加
    }

    // 深度优先搜索查找简单路径
    public void dfsSimplePath(int start, int end) {
        boolean[] visited = new boolean[vexnum];
        Stack<Integer> stack = new Stack<>();
        dfsHelper(start, end, visited, stack);
    }

    private boolean dfsHelper(int cur, int end, boolean[] visited, Stack<Integer> stack) {
        visited[cur] = true;
        stack.push(cur);

        if (cur == end) {
            printPath(stack);
            return true;
        }

        for (int next : adjList[cur]) {
            if (!visited[next]) {
                if (dfsHelper(next, end, visited, stack)) {
                    return true;
                }
            }
        }

        stack.pop(); // 回溯
        return false;
    }

    private void printPath(Stack<Integer> stack) {
        System.out.print("深度优先搜索简单路径: ");
        for (int vertex : stack) {
            System.out.print(vertices[vertex] + " ");
        }
        System.out.println();
    }

    // 广度优先搜索查找最短路径
    public void bfsShortestPath(int start, int end) {
        boolean[] visited = new boolean[vexnum]; // 访问标记
        int[] path = new int[vexnum]; // 记录路径
        Arrays.fill(path, -1); // 初始化路径为-1

        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int v = queue.poll();

            for (int next : adjList[v]) {
                if (!visited[next]) {
                    visited[next] = true;
                    path[next] = v;
                    queue.offer(next);

                    if (next == end) {
                        printShortestPath(path, start, end);
                        return;
                    }
                }
            }
        }

        System.out.println("使用广度优先搜索未找到路径。");
    }

    // 输出最短路径
    private void printShortestPath(int[] path, int start, int end) {
        Stack<Integer> stack = new Stack<>();
        for (int v = end; v != -1; v = path[v]) {
            stack.push(v);
        }

        System.out.print("广度优先搜索最短路径: ");
        while (!stack.isEmpty()) {
            System.out.print(vertices[stack.pop()] + " ");
        }
        System.out.println();
    }
}

public class MainList {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        GraphList graph = new GraphList(5);

        // 设置顶点
        graph.setVertex(0, 'A');
        graph.setVertex(1, 'B');
        graph.setVertex(2, 'C');
        graph.setVertex(3, 'D');
        graph.setVertex(4, 'E');

        // 添加边
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);

        // 用户输入起始和结束顶点
        System.out.print("请输入起始顶点（A-E）: ");
        char startVertex = scanner.next().charAt(0);
        System.out.print("请输入结束顶点（A-E）: ");
        char endVertex = scanner.next().charAt(0);

        int start = startVertex - 'A';
        int end = endVertex - 'A';

        // 查找从起始顶点到结束顶点的简单路径和最短路径
        graph.dfsSimplePath(start, end); // 深度优先搜索简单路径
        graph.bfsShortestPath(start, end); // 广度优先搜索最短路径

        scanner.close();
    }
}

/*
       A
      / \
     B   C
      \ / \
       D   E
     */